1. Field of the Invention
The present invention relates to a barrel shifter for symbols.
2. Discussion of the Related Art
An example of an application of a barrel shifter device relates to decoding symbols transmitted according to the DVB-S2 standard using an error correction code of the type LDPC (Low Density Parity Check).
FIG. 1 schematically shows a barrel shifter 10 (BS) receiving N symbols 12 in parallel arranged in a certain order, each symbol corresponding to a coded digital message of a determined number of bits nbit_data. The device 10 outputs in parallel N symbols 14, which correspond to N received symbols 12, on which a circular shift has been applied, to the left or to the right, by a number of positions which can be chosen to be between 0 and N−1. The barrel shifter 10 receives a control signal bs_ctrl from which the number of positions that the received symbols 12 are to be shifted can be determined.
FIG. 2 shows an example of a shift operation applied to eight symbols S0 to S7. The top line shows an example of the positioning of symbols S0 to S7 as received by the barrel shifter 10 and the bottom line shows the positioning of symbols output by the device 10 after the application of a circular shift to the right by three positions (which is equivalent to a circular shift to the left by five positions).
FIG. 3 shows an example of a classic implementation of a barrel shifter 10 receiving eight symbols and adapted to perform a circular shift to the right by 0 to 7 positions. The device 10 comprises three rows 15, 16, 17 of multiplexers. Each block 18 represents a multiplexing module receiving two symbols and outputting one of the two symbols received and comprising nbit_data multiplexers. Each solid arrow 19 corresponds to a path taken by a symbol, in other words, in practice, to connecting leads or connecting wires allowing the transmission of nbit_data bits. The multiplexers of the first, second and third rows 15, 16, 17 are respectively controlled by control signals bs_ctrl(0), bs_ctrl(1), and bs_ctrl(2).
Such a barrel shifter is said to have a logarithmic structure because each row of multiplexers allows a circular shift by a number of positions rising by a power of 2. Indeed, the first row 15 allows a circular shift to the right of one position (20), the second row 16 allows a circular shift to the right of two positions (21), and the third row 17 allows a circular shift to the right of four positions (22). By combining control bits bs_ctrl(0), bs_ctrl(1) and bs_ctrl(2), any shift from 0 to 7 positions can be performed.
In general, a barrel shifter 10 having a logarithmic structure and receiving N symbols requires, for performing a circular shift of anything from 0 to N−1 positions, ceil(log2(N)) rows of multiplexers where log2(N) is the logarithm to the base 2 of N, and ceil(log2(N)) is the greater integer value of log2(N). This device 10 therefore comprises N*nbit_data*ceil(log2(N)) multiplexers. The logarithmic structure allows the number of multiplexers necessary for providing a shift operation to be minimized.
During fabrication of a barrel shifter, computer aided design utilities are generally used that indicate the surface area that will theoretically be sufficient for arranging the multiplexers while taking into account the minimum separation distances to be provided between each multiplexer and the true surface area necessary for arranging the multiplexers and the connecting wires or tracks between them. The difference between the two surfaces is called the overhead.
One difficulty during application of a barrel shifter with logarithmic structure is due to the large irregularity in the lengths of the paths 19 and the large number of junctions between paths 19 required by the arrangement of multiplexers. This leads to a large increase of the surface overhead when the number of symbols and/or the number of bits per symbol becomes large. For example, for a decoder of LDPC code, the product of N*nbit_data can be larger than 2000. The surface overhead can therefore be larger than 300% for a barrel shifter with logarithmic structure. This results in barrel shifters which are very bulky.
Another drawback comes from the fact that an increase in the surface area of a barrel shifter brings about an increase in the length of at least some of the paths taken by symbols. A problem is that transmission time of a symbol along a path depends on the path length. If the transmission time of symbols (or at least of some of them) is too large, it may not be possible to perform a shift operation in one cycle of the clock which controls the operation of the barrel shifter. It is therefore necessary to provide, between the rows of the barrel shifter, memory elements (for example, latches) so that a shift operation can be performed over a number of clock cycles. The addition of memory elements contributes to the increase in the surface area occupied by the barrel shifter.
In certain cases, a vicious circle can result whereby the addition of memory elements brings about a rise in the length of paths of the symbols such that additional memory elements must be provided. It can therefore be necessary to impose a minimum duration for clock cycles below which a barrel shifter with a logarithmic structure having acceptable dimensions cannot be designed.